package com.tgy.algorithm.base._单调栈;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个只包含正整数的数组arr，arr中任何一个子数组sub一定都可以算出(sub累加和 )*(sub中的最小值)是什么。
 * 那么所有子数组中，这个值最大是多少?
 */
public class _数组中子数组最小值与子数组和的乘积_01 {

    public static int getMaxSub(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        int[] preSums = prefixSum(nums);
        Stack<List<Integer>> stack = new Stack<>();
        int value;
        int maxVal = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            value = nums[i];
            while (!stack.isEmpty()) {
                List<Integer> topList = stack.peek();
                if (nums[topList.get(0)] <= value) {
                    break;
                }

                stack.pop();
                for (Integer idx : topList) {
                    // 右边最小是 i;
                    if (stack.isEmpty()) {
                        maxVal = Math.max(maxVal,preSums[i - 1]* nums[idx]);
                    }else {
                        List<Integer> curList = stack.peek();
                        int preIdx = curList.get(curList.size() - 1);
                        maxVal = Math.max(maxVal,(preSums[i - 1] - preSums[preIdx]) * nums[idx]);
                    }
                }
            }

            if (!stack.isEmpty() && nums[stack.peek().get(0)] == value) {
                stack.peek().add(i);
            }else {
                ArrayList<Integer> ls = new ArrayList<>();
                ls.add(i);
                stack.push(ls);
            }
        }

        while (!stack.isEmpty()) {

            List<Integer> topList = stack.pop();
            for (Integer idx : topList) {
                // right 到len,
                if (stack.isEmpty()) {
                    maxVal = Math.max(maxVal,preSums[len - 1] * nums[idx]);
                }else {
                    List<Integer> curList = stack.peek();
                    Integer leftIndex = curList.get(curList.size() - 1);
                    maxVal = Math.max(maxVal,(preSums[len - 1] - preSums[leftIndex]) * nums[idx]);
                }
            }
        }

        return maxVal;
    }

    public static int[] prefixSum(int[] nums) {

        int len = nums.length;
        int[] preSums = new int[len];
        preSums[0] = nums[0];
        for (int i = 1; i < len; i++) {
            preSums[i] = preSums[i - 1] + nums[i];
        }

        return preSums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,2,2,3,2,3,4,5,3};
        int maxSub = getMaxSub(nums);
        System.out.println(maxSub);
    }
}
